package com.dyz.leetcode._07_hashSearch;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class _128_longestConsecutive {
    public int longestConsecutive(int[] nums) {
        Arrays.sort(nums);
        int ans = 1;
        int count = 1;
        for(int i=1; i<nums.length-1;i++){
            if (nums[i] == nums[i + 1]) {continue;}
            if(nums[i+1]==nums[i]+1){
                count++;
            }else {
                ans = Math.max(ans, count);
                count=1;
            }

        }
        return Math.max(ans, count);
    }

    public int longestConsecutive1(int[] nums) {
        if (nums.length < 2) {return nums.length;}

        Set<Integer> set = new HashSet<>();
        for (Integer num : nums) {set.add(num);}

        int ans = 1;
        for (int num : nums) {
            // 这里会存在重复计算，为什么会产生以及如何解决，请参考 issue：
            // https://gitee.com/douma_edu/douma_algo_training_camp/issues/I4H4RZ
            if (set.contains(num - 1)) {continue;}

            int currNum = num;
            int count = 1;
            while (set.contains(currNum + 1)) {
                currNum += 1;
                count += 1;
            }

            ans = Math.max(ans, count);
        }

        return ans;
    }
}
